package edu.gatech.cuckoo;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * This class will represent a modified linear probing hash table. The
 * modification is specified in the comments for the put method.
 */
public class HashTable<K, V> {

	/**
	 * Constant determining the max load factor
	 */
	private final double MAX_LOAD_FACTOR = 0.71;

	/**
	 * Constant determining the initial table size
	 */
	private final int INITIAL_TABLE_SIZE = 17;

	/**
	 * Number of elements in the table
	 */
	private int size;

	/**
	 * The backing array of this hash table
	 */
	private MapEntry<K, V>[] table;

	// Hash functions
	private GenericHashFunction<K, V>[] functions;

	private Random rand;

	// private int oldFactor;

	/**
	 * Initialize the instance variables Initialize the backing array to the
	 * initial size given
	 */
	@SuppressWarnings("unchecked")
	public HashTable() {
		rand = new Random();
		functions = new GenericHashFunction[2];
		table = new MapEntry[INITIAL_TABLE_SIZE];
		size = 0;
		newHash();
	}

	/**
	 * Generates new hash functions for reindexing the hash table.
	 */
	private void newHash() {
		// Keep track of previously used uniqueness factors so that we don't
		// repeat hash functions (unlikely, I know).
		ArrayList<Integer> previousFactors = new ArrayList<Integer>();

		// Add any currently used uniqueness factors to the list.
		for (int i = 0; i < functions.length; i++) {
			if (functions[i] != null) {
				previousFactors.add(functions[i].getFactor());
			}
		}

		// Generate new hash functions.
		for (int i = 0; i < functions.length; i++) {
			int newFactor = rand.nextInt();
			// Make sure we only create a hash function with a new uniqueness
			// factor.
			while (previousFactors.contains(newFactor)) {
				newFactor = rand.nextInt();
			}
			
			functions[i] = new GenericHashFunction<K, V>(newFactor);

			// Make sure that successive functions can't have the same factor.
			previousFactors.add(newFactor);
		}
	}

	/**
	 * Add the key value pair in the form of a MapEntry using HashFunction if
	 * the key already exist, replace the old value with the new value if the
	 * position is unavailable, kick out the old key and replace it with the new
	 * key, and rehash the old key with an updated Factor
	 * 
	 * @param key
	 *            This will never be null
	 * @param value
	 *            This can be null
	 */
	public void put(K key, V value) {
		if (key == null)
			return;
		// Replace current value if key is already in the table.
		for (int i = 0; i < functions.length; i++) {
			// Locate the value in the table.
			int index = functions[i].hashCode(key) % table.length;
			MapEntry<K, V> entry = table[index];

			// Determine if this index in table already contains this key.
			if (entry != null && entry.getKey().equals(key)) {
				// Replace the existing value with the given one.
				entry.setValue(value);
				return;
			}
		}

		/*
		 * By this point, we have determined that the value is not in the hash
		 * table. We must insert it.
		 */
		// Check for load factor violation before adding
		if ((size + 1) / table.length > MAX_LOAD_FACTOR)
			regrow();

		// Continuously try to insert the value into the hash table. This is
		// where we rehash after too many attempts.
		MapEntry<K, V> insertEntry = new MapEntry<K, V>(key, value);
		while (true) {
			// Insert into table and rehash if an element is displaced.
			insertEntry = insert(insertEntry, 0, -1);
			
			if(insertEntry == null) break;
			newHash();
			rehash();
		}
		
		size++;
	}

	/**
	 * Rehashes elements into it with the new hash functions.
	 */
	private void rehash() {
		MapEntry<K, V>[] temp = table;
		table = new MapEntry[table.length];
		for (MapEntry<K, V> entry : temp) {
			while(entry != null) {
				entry = insert(entry, 0, -1);
			}
		}
	}

	/**
	 * Attempts to insert a given node into the hash table, displacing nodes for
	 * several iterations, if necessary.
	 * 
	 * @param insertMe
	 *            The entry to be inserted into the hash table.
	 * @return The last displaced entry, or null if all conflicts were resolved.
	 */
	private MapEntry<K, V> insert(MapEntry<K, V> insertMe, int level, int currentIndex) {

		// Simply return the entry if we are too many recursive calls deep.
		if (level > table.length || insertMe == null) {
			return insertMe;
		}
		
		// Obtain the "alternate" index for the given entry
		int index = functions[0].hashCode(insertMe.getKey()) % table.length;
		if (index == currentIndex) {
			index = functions[1].hashCode(insertMe.getKey()) % table.length;
		}
		MapEntry<K, V> current = table[index];
		
		// Insert entry at its alternate index
		table[index] = insertMe;
		if (current == null) {
			return null;
		} else {
			return insert(current, level + 1, index);
		}
	}

	/**
	 * Regrows the table to twice its length + 1 and reinserts the existing
	 * elements.
	 */
	@SuppressWarnings("unchecked")
	private void regrow() {
		MapEntry<K, V>[] temp = table;
		table = new MapEntry[table.length * 2 + 1];
		for (MapEntry<K, V> entry : temp) {
			if (entry != null) {
				put(entry.getKey(), entry.getValue());
			}
		}
	}

	/**
	 * Remove the entry with the given key.
	 * 
	 * @param key
	 * @return The value associated with the key removed, null if the key is not found.
	 */
	public V remove(K key) {
		// Check locations yielded by both hash functions.
		for (int i = 0; i < functions.length; i++) {
			int index = functions[i].hashCode(key) % table.length;
			MapEntry<K, V> entry = table[index];
			
			// If the node is found, delete it and return its value
			if (entry != null && entry.getKey().equals(key)) {
				V ret = entry.getValue();
				table[index] = null;
				size--;
				return ret;
			}
		}
		
		return null;
	}

	/**
	 * Checks whether an entry with the given key exists in the hash table
	 * 
	 * @param key
	 * @return
	 */
	public boolean contains(K key) {
		// Check in each position that the key could be inserted.
		for(int i = 0; i < functions.length; i++) {
			int index = functions[i].hashCode(key) % table.length;
			MapEntry<K, V> entry = table[index];
			
			// Determine if entry is what we are looking for.
			if (entry != null && entry.getKey().equals(key)) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Return a collection of all the values
	 * 
	 * We recommend using an ArrayList here
	 * 
	 * @return
	 */
	public Collection<V> values() {
		Collection<V> list = new ArrayList<V>();
		for (MapEntry<K, V> entry : table) {

			// Ignore "empty" entries
			if (entry != null) {

				list.add(entry.getValue());
			}
		}
		return list;
	}

	/**
	 * Return a set of all the distinct keys
	 * 
	 * We recommend using a HashSet here
	 * 
	 * Note that the map can contain multiple entries with the same key
	 * 
	 * @return
	 */
	public Set<K> keySet() {
		Set<K> list = new HashSet<K>();
		for (MapEntry<K, V> entry : table) {

			// Ignore "empty" entries
			if (entry != null) {

				// Traverse chained lists of entries
				list.add(entry.getKey());
			}
		}
		return list;
	}

	/**
	 * Return a set of all the unique key-value entries
	 * 
	 * Note that two map entries with both the same key and value could exist in
	 * the map.
	 * 
	 * @return
	 */
	public Set<MapEntry<K, V>> entrySet() {
		Set<MapEntry<K, V>> set = new HashSet<MapEntry<K, V>>();
		for (MapEntry<K, V> entry : table) {
			// Add every valid entry to the set.
			if (entry != null) {
				set.add(entry);
			}
		}
		return set;
	}

	/**
	 * Clears the hash table
	 */
	@SuppressWarnings("unchecked")
	public void clear() {
		table = new MapEntry[INITIAL_TABLE_SIZE];
		size = 0;
	}

	/*
	 * The following methods will be used for grading purposes do not modify
	 * them
	 */

	public int size() {
		return size;
	}

	public void setSize(int size) {
		this.size = size;
	}

	public MapEntry<K, V>[] getTable() {
		return table;
	}

	public void setTable(MapEntry<K, V>[] table) {
		this.table = table;
	}
}
